package cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure;

import cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure.util.BTree;
import cn.edu.neu.softlab.jason.offer.jianzhioffer.datastructure.util.BTreeNode;

import java.util.ArrayList;

/**
 * 剑指offer-面试6
 * 重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
 */

public class Mianshi6 {
    public static void main(String[] args) {
        ArrayList<Integer> firstorderlist = new ArrayList<>();
        ArrayList<Integer> inorderlist = new ArrayList<>();
        ArrayList<Integer> lastorderlist = new ArrayList<>();

        firstorderlist.add(1);
        firstorderlist.add(2);
        firstorderlist.add(4);
        firstorderlist.add(7);
        firstorderlist.add(3);
        firstorderlist.add(5);
        firstorderlist.add(6);
        firstorderlist.add(8);

        inorderlist.add(4);
        inorderlist.add(7);
        inorderlist.add(2);
        inorderlist.add(1);
        inorderlist.add(5);
        inorderlist.add(3);
        inorderlist.add(8);
        inorderlist.add(6);

        lastorderlist.add(7);
        lastorderlist.add(4);
        lastorderlist.add(2);
        lastorderlist.add(5);
        lastorderlist.add(8);
        lastorderlist.add(6);
        lastorderlist.add(3);
        lastorderlist.add(1);

        BTreeNode root = getTreeWithInorderandFirstorder(inorderlist, firstorderlist);
        BTree.lastOrderTraverse(root);
        System.out.println();
        BTreeNode firstroot = getTreeWithInorderandLastOrder(inorderlist, lastorderlist);
        BTree.firstOrderTraverse(firstroot);

        ArrayList<Integer> firstorderlist1 = new ArrayList<>();
        ArrayList<Integer> inorderlist1 = new ArrayList<>();
        ArrayList<Integer> lastorderlist1 = new ArrayList<>();

        firstorderlist1.add(1);
        firstorderlist1.add(2);
        firstorderlist1.add(4);
        firstorderlist1.add(5);
        firstorderlist1.add(6);
        firstorderlist1.add(7);
        firstorderlist1.add(8);
        firstorderlist1.add(9);
        firstorderlist1.add(3);

        inorderlist1.add(4);
        inorderlist1.add(6);
        inorderlist1.add(8);
        inorderlist1.add(7);
        inorderlist1.add(9);
        inorderlist1.add(5);
        inorderlist1.add(2);
        inorderlist1.add(1);
        inorderlist1.add(3);

        lastorderlist1.add(8);
        lastorderlist1.add(9);
        lastorderlist1.add(7);
        lastorderlist1.add(6);
        lastorderlist1.add(5);
        lastorderlist1.add(4);
        lastorderlist1.add(2);
        lastorderlist1.add(3);
        lastorderlist1.add(1);

        BTreeNode root1 = getTreeWithInorderandFirstorder(inorderlist1, firstorderlist1);
        System.out.println();
        BTree.lastOrderTraverse(root1);
        System.out.println();
        BTreeNode firstroot1 = getTreeWithInorderandLastOrder(inorderlist1, lastorderlist1);
        BTree.firstOrderTraverse(firstroot1);

    }

    public static BTreeNode getTreeWithInorderandFirstorder(ArrayList<Integer> inorderlist, ArrayList<Integer> firstorderlist) {
        return getTreeWithInorderandFirstorder(inorderlist, firstorderlist, 0, inorderlist.size() - 1, 0, firstorderlist.size() - 1);
    }

    public static BTreeNode getTreeWithInorderandLastOrder(ArrayList<Integer> inorderlist, ArrayList<Integer> lastorderlist) {
        return getTreeWithInorderandLastOrder(inorderlist, lastorderlist, 0, inorderlist.size() - 1, 0, lastorderlist.size() - 1);
    }

    private static BTreeNode getTreeWithInorderandFirstorder(ArrayList<Integer> inorderlist, ArrayList<Integer> firstorderlist,
                                                             int inlow, int inup, int firstlow, int firstup) {
        if (firstlow > firstup) {
            return null;
        } else if (firstlow == firstup) {
            return new BTreeNode(firstorderlist.get(firstlow));
        }
        BTreeNode root = null;
        int pos = -1;
        for (int i = inlow; i <= inup; i++) {
            if (inorderlist.get(i) == firstorderlist.get(firstlow)) {
                pos = i;
                root = new BTreeNode(firstorderlist.get(firstlow));
                break;
            }
        }
        if (pos != -1) {
            int leftlength = pos - inlow;
            BTreeNode leftnode = getTreeWithInorderandFirstorder(inorderlist, firstorderlist, inlow, pos - 1, firstlow + 1, firstlow + leftlength);
            root.setLeft(leftnode);
            BTreeNode rightnode = getTreeWithInorderandFirstorder(inorderlist, firstorderlist, pos + 1, inup, firstlow + leftlength + 1, firstup);
            root.setRight(rightnode);
        }
        return root;
    }

    private static BTreeNode getTreeWithInorderandLastOrder(ArrayList<Integer> inorderlist, ArrayList<Integer> lastorderlist, int inlow, int inup, int lastlow, int lastup) {
        if (lastlow > lastup) {
            return null;
        } else if (lastlow == lastup) {
            return new BTreeNode(lastorderlist.get(lastup));
        }

        int pos = -1;
        BTreeNode root = null;

        for (int i = inlow; i <= inup; i++) {
            if (inorderlist.get(i) == lastorderlist.get(lastup)) {
                pos = i;
                root = new BTreeNode(lastorderlist.get(lastup));
                break;
            }
        }

        if (pos != -1) {
            int leftlength = pos - inlow;
            BTreeNode leftnode = getTreeWithInorderandLastOrder(inorderlist, lastorderlist, inlow, pos - 1, lastlow, lastlow + leftlength - 1);
            root.setLeft(leftnode);
            BTreeNode rightnode = getTreeWithInorderandLastOrder(inorderlist, lastorderlist, pos + 1, inup, lastlow + leftlength, lastup - 1);
            root.setRight(rightnode);
        }
        return root;
    }

}
